%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{Positive integer $n$ and a probability $0 < p < 1$.}
%%
%% output
\KwOut{A random sparse graph from $G(n,p)$.}
\BlankLine
%%
%% algorithm body
$G \assign \overline{K_n}$\;
$u \assign 1$\;
$v \assign -1$\;
\While{$u < n$}{
  $r \assign$ draw uniformly at random from interval $(0,1)$\;
  $v \assign v + 1 + \lfloor \ln(1 - r) / \ln(1 - p) \rfloor$\;
  \While{\rm $v \geq u$ and $u < n$}{
    $v \assign v - u$\;
    $u \assign u + 1$\;
  }
  \If{$u < n$}{
    add edge $uv$ to $G$\;
  }
}
\Return $G$\;
